package com.github.hgkmail.hello.leetcode101.pointer.graph.mst;

import com.github.hgkmail.hello.leetcode101.base.UF;
import org.apache.shiro.crypto.hash.Hash;

import java.util.*;

//最小生成树
//教训：邻接表只使用List<List<Integer>>，不要用数组。
//邻接矩阵：int[][] graph
//邻接表：List<List<Integer>> graph
//不用混用，不要学LeetCode的定义。
public class LC1584MinCostToConnectAllPoints {
    class Edge {
        int u,v,dist;
        public Edge() {}
        public Edge(int uu,int vv,int dd) {
            u=uu;
            v=vv;
            dist=dd;
        }
    }
    //kruskal算法，检查边的贪心算法，用于稀疏图，代码框架：PriorityQueue<Edge> + UnionFind<Vertex>
    //这道题相当于稠密图，不太适合kruskal算法
    public int minCostConnectPoints(int[][] points) {
        int vertexNum=points.length;
        if (vertexNum<=0) {
            return 0;
        }
        //pq<edge> + uf<vertex>
        PriorityQueue<Edge> heap= new PriorityQueue<>(vertexNum * vertexNum, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.dist - o2.dist;
            }
        });
        UF uf = new UF(vertexNum);
        //生成边
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                if (i>=j) {
                    continue;
                }
                int dist = Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);
                heap.offer(new Edge(i, j, dist));
            }
        }
        //检查所有边
        int cost=0;
        while (!heap.isEmpty()) {
            Edge edge = heap.poll();
            if (uf.isConnected(edge.u, edge.v)) {
                continue;
            }
            uf.union(edge.u, edge.v);
            cost += edge.dist;
        }
        return cost;
    }

    //prim算法，检查点的贪心算法，用于稠密图，代码框架：PriorityQueue<Edge> + HashSet<Vertex> + AdjGraph(List<List<Integer>>)
    //这道题相当于稠密图，适合prim算法
    public int minCostConnectPoints2(int[][] points) {
        int vertexNum=points.length;
        if (vertexNum<=0) {
            return 0;
        }
        //pq<edge> + set + graph<adj>
        PriorityQueue<Edge> heap= new PriorityQueue<>(vertexNum * vertexNum, new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.dist - o2.dist;
            }
        });
        Set<Integer> usedPoints = new HashSet<>();
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            graph.add(new ArrayList<>());
        }
        //生成邻接表，注意：二维坐标不是邻接点，元素才是邻接点。。。
        for (int i = 0; i < vertexNum; i++) {
            for (int j = 0; j < vertexNum; j++) {
                if (i==j) {
                    continue;
                }
                graph.get(i).add(j);
            }
        }
        //检查所有的点
        int cost=0;
        for (int i = 0; i < vertexNum; i++) { //这个循环可以应付多连通的图
            if (usedPoints.contains(i)) {
                continue;
            }
            //加入一个点到set，将它的邻接边入队
            usedPoints.add(i);
            for (int j:graph.get(i)) {
                int dist = Math.abs(points[i][0]-points[j][0])+Math.abs(points[i][1]-points[j][1]);
                heap.offer(new Edge(i, j, dist));
            }
            //取出最小的邻接边
            while (!heap.isEmpty()) {
                Edge edge = heap.poll();
                int v=edge.v;
                if (usedPoints.contains(v)) {
                    continue;
                }
                //是新的点，加入到set，并将其邻接边入队
                usedPoints.add(v);
                cost+=edge.dist;
                for (int j:graph.get(v)) {
                    int dist = Math.abs(points[v][0]-points[j][0])+Math.abs(points[v][1]-points[j][1]);
                    heap.offer(new Edge(v, j, dist));
                }
            }
        }

        return cost;
    }

    public static void main(String[] args) {
        System.out.println(new LC1584MinCostToConnectAllPoints().minCostConnectPoints2(new int[][]{{0,0},{1,1},{1,0},{-1,1}}));
    }
}
